package main

import (
	"fmt"
)

/**
执行用时：4 ms, 在所有 Go 提交中击败了92.31%的用户
内存消耗：4.1 MB, 在所有 Go 提交中击败了25.91%的用户
 */
func trap(height []int) int {

	n := len(height)
	if n == 0 { return 0 }

	left_max := make([]int, n)
	left_max[0] = height[0]
	for i := 1; i < n; i++ { left_max[i] = max(left_max[i - 1], height[i]) }

	right_max := make([]int, n)
	right_max[n - 1] = height[n - 1]
	for i := n - 2; i >= 0; i-- { right_max[i] = max(right_max[i + 1], height[i]) }

	res := 0
	for i := 0; i < n; i++ {
		res += min(left_max[i], right_max[i]) - height[i];
	}
	return res
}

// 求最大值
func max(a int, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

// 求最小值
func min(a int, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func main() {

	heights := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
	fmt.Println(trap(heights))  // 6
}
